{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Digit One"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countDigitOne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数字 1 的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数 <code>n</code>，计算所有小于等于 <code>n</code> 的非负整数中数字 <code>1</code> 出现的个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 13\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-digit-one](https://leetcode.cn/problems/number-of-digit-one/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-digit-one](https://leetcode.cn/problems/number-of-digit-one/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['13', '0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        res = 0\n",
    "        m = 1\n",
    "        while m <= n:\n",
    "            res += (1 + (n // m - 1) // 10)*m\n",
    "            if (n // m) % 10 == 1:\n",
    "                res += 1 - m + n % m\n",
    "            m *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        # mulk 表示 10^k\n",
    "        # 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）\n",
    "        # 但为了让代码看起来更加直观，这里保留了 k\n",
    "        k, mulk = 0, 1\n",
    "        ans = 0\n",
    "        while n >= mulk:\n",
    "            ans += (n // (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)\n",
    "            k += 1\n",
    "            mulk *= 10\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        # 将 n 转换为字符串 s\n",
    "        s = str(n)\n",
    "        \n",
    "        @cache\n",
    "        # pos: 第 pos 个数位\n",
    "        # cnt: 之前数字 1 出现的个数。\n",
    "        # isLimit: 表示是否受到选择限制。如果为真，则第 pos 位填入数字最多为 s[pos]；如果为假，则最大可为 9。\n",
    "        def dfs(pos, cnt, isLimit):\n",
    "            if pos == len(s):\n",
    "                return cnt\n",
    "            \n",
    "            ans = 0            \n",
    "            # 不需要考虑前导 0，则最小可选择数字为 0\n",
    "            minX = 0\n",
    "            # 如果受到选择限制，则最大可选择数字为 s[pos]，否则最大可选择数字为 9。\n",
    "            maxX = int(s[pos]) if isLimit else 9\n",
    "            \n",
    "            # 枚举可选择的数字\n",
    "            for d in range(minX, maxX + 1): \n",
    "                ans += dfs(pos + 1, cnt + (d == 1), isLimit and d == maxX)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        def dp(n):\n",
    "            t={0:0,1:1,2:1,3:1,4:1,5:1,6:1,7:1,8:1,9:1,99:20,999:300,9999:4000,99999:50000,999999:600000,9999999:7000000}\n",
    "            if n in t:return t[n]\n",
    "            bb=10**(len(str(n))-1)\n",
    "            if n<bb*2:return (n-bb+1)+dp(n-bb)+dp(bb-1)\n",
    "            else:return dp(bb-1)*(n//bb)+dp(n%bb)+bb\n",
    "        return dp(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "\n",
    "        L = len(str(n)) // 2\n",
    "\n",
    "        base = 10 ** L\n",
    "\n",
    "        head = n // base\n",
    "        tail = n % base\n",
    "\n",
    "        m = max(base, head)\n",
    "        \n",
    "        memo = [0]*(m+1)\n",
    "        for i in range(1, m+1):\n",
    "            memo[i] = memo[i // 10] + (i % 10 == 1)\n",
    "\n",
    "        res = (tail+1) * memo[head]\n",
    "        cur = 0\n",
    "        for i in range(m):\n",
    "            cur += memo[i]\n",
    "        \n",
    "            if i == head-1:\n",
    "                res += cur * base\n",
    "            \n",
    "            if i == tail:\n",
    "                res += cur\n",
    "            \n",
    "            if i == base - 1:\n",
    "                res += cur * head\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        digit = 1\n",
    "        res = 0\n",
    "        high = n//10\n",
    "        low = 0\n",
    "        cur = n%10\n",
    "        \n",
    "        while high or cur:\n",
    "            if cur == 0:\n",
    "                res+=high*digit\n",
    "            elif cur == 1:\n",
    "                res += high*digit + low + 1\n",
    "            else:\n",
    "                res += (high+1)*digit\n",
    "            low += cur * digit\n",
    "            cur = high%10\n",
    "            high = high//10\n",
    "            digit *= 10\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        mulk = 1\n",
    "        res = 0\n",
    "        while mulk <= n:\n",
    "            res += (n//(mulk*10))*mulk + min(max(n%(mulk*10)-mulk+1, 0), mulk)\n",
    "            mulk *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "\n",
    "        digital, res = 1, 0\n",
    "        num = n\n",
    "        hight = num//10\n",
    "        low = 0\n",
    "        cur = num%10\n",
    "        while hight!=0 or cur!=0:\n",
    "\n",
    "            if cur == 0:\n",
    "                res+=hight*digital\n",
    "            if cur == 1:\n",
    "                res+=(hight)*digital+low+1\n",
    "            if cur>1:\n",
    "                res+=(hight+1)*digital\n",
    "            \n",
    "            low+=digital*cur\n",
    "            digital*=10\n",
    "            cur = hight%10\n",
    "            hight //=10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "            elif cur == 1:\n",
    "                res += high * digit + low + 1\n",
    "            else:\n",
    "                res += (high + 1) * digit\n",
    "            \n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        digit = 1\n",
    "        count = 0\n",
    "        num = n\n",
    "        while num != 0:\n",
    "            if str(num)[-1] == '1':\n",
    "                count += (num // 10) * digit + n % digit + 1\n",
    "            elif  str(num)[-1] == '0':\n",
    "                count += (num // 10) * digit\n",
    "            else:\n",
    "                count += ((num // 10) + 1) * digit\n",
    "            num = num // 10\n",
    "            digit = 10 *digit\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        k = 1\n",
    "        ans = 0\n",
    "        while k <= n:\n",
    "            ans += (n // (k * 10)) * k + min(max(n % (k * 10) - k + 1, 0), k)\n",
    "            k *= 10\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "\n",
    "        k, mulk = 0, 1\n",
    "        ans = 0\n",
    "        while n >= mulk:\n",
    "            ans += (n // (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)\n",
    "            k += 1\n",
    "            mulk *= 10\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        times=0\n",
    "        for i in range(0,11):\n",
    "            if n//(10**i)==0:\n",
    "                times=i-1\n",
    "                break\n",
    "        def opr(num,t):\n",
    "            if t==-1:\n",
    "                return 0\n",
    "            if t==0:\n",
    "                if num==0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "            lv=10**t\n",
    "            n=num%lv\n",
    "            m=num//lv\n",
    "            if m==0:\n",
    "                return opr(m+num,t-1)\n",
    "            if m>0:\n",
    "                if m==1:\n",
    "                    return n+1+opr(n,t-1)+opr(lv-1,t-1)\n",
    "                else:\n",
    "                    return lv+opr(n,t-1)+m*opr(10**t-1,t-1)\n",
    "        \n",
    "        res=opr(n,times)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        sn = str(n)\n",
    "        N = len(sn)\n",
    "        dp = [0]*(N+1)\n",
    "        dp[0],dp[1]=0,1\n",
    "        for i in range(1,N):\n",
    "            dp[i] = 10*dp[i-1] + 10**(i-1)\n",
    "        ret = 1 if n%10>=1 else 0\n",
    "        for i in range(1,N):\n",
    "            p = int(sn[N-1-i])\n",
    "\n",
    "            if p>1:\n",
    "                ret = (p)*dp[i]+ret + 10**i \n",
    "            elif p==1:\n",
    "                ret = dp[i]+ret+int(sn[N-i:])+1\n",
    "        #     print(p,ret)\n",
    "        # print(dp)\n",
    "        return ret "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        digit, res = 1,0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1:res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "\n",
    "        count = 0\n",
    "        digit = 1\n",
    "        high = n // 10\n",
    "        cur = n % 10\n",
    "        low = 0\n",
    "\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                count += high * digit\n",
    "            elif cur == 1:\n",
    "                count += high * digit + low + 1\n",
    "            else:\n",
    "                count += (high + 1) * digit\n",
    "\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        m = 1\n",
    "        res = 0\n",
    "        while n >= m:\n",
    "            res += (1 + (n // m -1) // 10) * m\n",
    "            if n // m % 10 == 1:\n",
    "                res = res - m + 1 + n % m\n",
    "            m *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high or cur:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 先计算100内的，再考虑3位数、4位数，发现规律\n",
    "    # 类似动态规划\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        dp = [0]*100\n",
    "        dp[0] = 0\n",
    "        for i in range(100):\n",
    "            if i == 1:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            elif i < 10:\n",
    "                dp[i] = dp[i-1]\n",
    "            elif i == 10:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            elif i == 11:\n",
    "                dp[i] = dp[i-1] + 2\n",
    "            elif i < 20:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            elif i % 10 == 1:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        m = len(str(n))\n",
    "        if m <= 2: # 2位数\n",
    "            return dp[n]\n",
    "        # if m == 3: # 3位数\n",
    "        #     dp_99 = self.countDigitOne(99)\n",
    "        #     if n < 200:\n",
    "        #         # dp[n] = dp[100] + dp[n-100] + dp[n%100]\n",
    "        #         return dp_99 + 1 + self.countDigitOne(n-100) + (n%100)\n",
    "        #     else:\n",
    "        #         b = int(n/100)\n",
    "        #         dp_b99 = dp_99+100\n",
    "        #         for i in range(1, b):\n",
    "        #             dp_b99 += dp_99\n",
    "        #         return dp_b99 + self.countDigitOne(n-b*100)\n",
    "        # if m == 4: # 4位数\n",
    "        #     dp_999 = self.countDigitOne(999)\n",
    "        #     if n < 2000:\n",
    "        #         return dp_999 + 1 + self.countDigitOne(n-1000) + (n%1000)\n",
    "        #     else:\n",
    "        #         b = int(n/1000)\n",
    "        #         dp_b999 = dp_999+1000\n",
    "        #         for i in range(1, b):\n",
    "        #             dp_b999 += dp_999\n",
    "        #         return dp_b999 + self.countDigitOne(n-b*1000)\n",
    "        first = int(n/10**(m-1)) # 首位数\n",
    "        dp_first_99 = self.countDigitOne(10**(m-1)-1)\n",
    "        if first == 1:\n",
    "            return dp_first_99 + 1 + self.countDigitOne(n-10**(m-1)) + (n%10**(m-1))\n",
    "        else:\n",
    "            b = int(n/10**(m-1))\n",
    "            dp_second_999 = dp_first_99+10**(m-1)\n",
    "            for i in range(1, b):\n",
    "                dp_second_999 += dp_first_99\n",
    "            return dp_second_999 + self.countDigitOne(n-b*10**(m-1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        k, mulk = 0, 1\n",
    "        res = 0\n",
    "        while n >= mulk:\n",
    "            res += (n // (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)\n",
    "            k += 1\n",
    "            mulk *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        num_str = str(n)\n",
    "        dp = [1]\n",
    "        for i in range(1, len(num_str) - 1):\n",
    "            dp.append(10 ** i + 10 * dp[- 1])\n",
    "        pre_num = int(num_str[-1])\n",
    "        pre_res = 1 if pre_num else 0\n",
    "        for i in range(len(num_str) - 2, -1, -1):\n",
    "            num = int(num_str[i])\n",
    "            if not num:\n",
    "                continue\n",
    "            level = len(num_str) - 1 - i\n",
    "            if num > 1:\n",
    "                pre_res += num * dp[level - 1] + 10 ** level\n",
    "            else:\n",
    "                pre_res += dp[level - 1] + pre_num + 1\n",
    "            pre_num = num * 10 ** level + pre_num\n",
    "        return pre_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 反向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # dp(length) 意义是返回长度为 length 的包含前缀 0 整数有多少个 1\n",
    "#         @cache\n",
    "#         def dp(length: int) -> int:\n",
    "#             if length <= 1: return length\n",
    "#             return dp(length - 1) * 10 + 10 ** (length - 1)\n",
    "#         li = []\n",
    "#         tmp = n\n",
    "#         while tmp:\n",
    "#             li.append(tmp % 10)\n",
    "#             tmp //= 10\n",
    "#         ones = res = 0\n",
    "#         for length in range(len(li) - 1, -1, -1):\n",
    "#             if li[length] == 0: continue\n",
    "#             tens = 10 ** length\n",
    "#             res += (dp(length) + ones * tens) * li[length]\n",
    "#             print(dp(length), ones * tens, li[length])\n",
    "#             if li[length] > 1: res += tens\n",
    "#             else: res, ones = res + 1, ones + 1\n",
    "#         return res\n",
    "\n",
    "# 正向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         res, tens, dps, suff = 0, 1, 0, 0\n",
    "#         while n:\n",
    "#             num, n = n % 10, n // 10\n",
    "#             if num > 0:\n",
    "#                 res += dps * num + tens\n",
    "#                 if num == 1: res += suff + 1 - tens\n",
    "#             dps = dps * 10 + tens\n",
    "#             # print(dps)\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        res, tens, dps, suff = 0, 1, 0, 0\n",
    "        time = -1\n",
    "        while n:\n",
    "            num, n, time = n % 10, n // 10, time + 1\n",
    "            if num > 0:\n",
    "                dps = time * tens // 10\n",
    "                res += dps * num + tens\n",
    "                if num == 1: res += suff + 1 - tens\n",
    "                \n",
    "            \n",
    "            # print(dps)\n",
    "            suff += num * tens\n",
    "            tens *= 10\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        if n==0:    return 0\n",
    "        b=0\n",
    "        tmp=n\n",
    "        while tmp:   \n",
    "            tmp//=10\n",
    "            b+=1\n",
    "        ap=[1,]+[0]*(b-1)\n",
    "        for i in range(b-1):\n",
    "            ap[i+1]+=ap[i]*9+10**(i+1)+ap[i]\n",
    "        res=0\n",
    "        print(ap)\n",
    "        for i in range(b-1):\n",
    "            j=b-1-i\n",
    "            v=n//10**j\n",
    "            n-=v*10**j\n",
    "            if v==0:\n",
    "                continue\n",
    "            elif v==1:\n",
    "                res+=v*ap[j-1]+n+1\n",
    "            else:\n",
    "                res+=v*ap[j-1]+10**j\n",
    "            #print(v,res)\n",
    "        if n>=1:    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        base = 1\n",
    "        count = 0\n",
    "        while(n>=base):\n",
    "            nex_base = base*10\n",
    "            cnt,res = divmod(n,nex_base)\n",
    "            # count += cnt+min(max(res - base+1,0),base)\n",
    "            count += cnt*base+min(max(res - base+1,0),base)\n",
    "            base = nex_base\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        res = 0\n",
    "        digit = 1\n",
    "        high = n // 10\n",
    "        low = 0\n",
    "        cur = n % 10\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "            elif cur == 1:\n",
    "                res += high * digit + low + 1\n",
    "            else:\n",
    "                res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        return self.countDigitOneRecu(str(n))\n",
    "    \n",
    "    def countDigitOneRecu(self, n):\n",
    "        if len(n) == 1:\n",
    "            return 0 if n == \"0\" else 1\n",
    "        first_num = 0\n",
    "        if n[0] == \"1\":\n",
    "            first_num = int(n[1:])+1\n",
    "        elif n[0] > \"1\":\n",
    "            first_num = 10**len(n[1:])\n",
    "        other_num = int(n[0])*len(n[1:])*10**len(n[2:])\n",
    "        recu_num = self.countDigitOneRecu(n[1:])\n",
    "        return first_num+other_num+recu_num # 核心代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        def test(k):\n",
    "            return k * 10 ** (k-1)\n",
    "\n",
    "        s = str(n)\n",
    "        m = len(s)\n",
    "\n",
    "        def dfs(i,isLimit):\n",
    "            \n",
    "            if i == m-1:\n",
    "                return 1 if s[i] >= \"1\" else 0\n",
    "            \n",
    "\n",
    "                res = dfs(i+1, False) \n",
    "            low = 0 \n",
    "            up = int(s[i]) if isLimit else 10 # [low, up)\n",
    "            # up = bi if isLimit else 9\n",
    "            # 余位是 1-9999 还是 bi+1 bi+2 ...\n",
    "            res = 0\n",
    "            if isLimit:\n",
    "                res = dfs(i+1, True) # i取bi\n",
    "            # 当i不取bi时  x[i+1 ... m-1] 的所有变化能生成的1， m-i-1位数\n",
    "            # print(up-low, m-1-i, test(m-1-i)) # 01 11\n",
    "            res += (up-low) * test(m-1-i)\n",
    "            # 考虑1\n",
    "            # 只要1属于 [low, up) 区间 1[i+1,...m-1] 产生的1\n",
    "            if 1 == up:\n",
    "                # print(s[i+1:], int(s[i+1:]))\n",
    "                res += (int(s[i+1:]) + 1)\n",
    "            elif 1 < up:\n",
    "                res += 10 ** (m-1-i)\n",
    "            return res\n",
    "        return dfs(0, True)\n",
    "            \n",
    "        # 0x 1x 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n < 10:\n",
    "            return 1\n",
    "        return count(str(n))\n",
    "    \n",
    "@cache\n",
    "def count(n):\n",
    "    if len(n) == 1:\n",
    "        return int(n != '0')\n",
    "    if n[0] == '0':\n",
    "        return count(n[1:])\n",
    "    if n[0] == '1':\n",
    "        return int(n[1:]) + 1 + count(n[1:]) + count('9'*(len(n)-1))\n",
    "    else:\n",
    "        return int('1'+'0'*(len(n)-1)) + count(n[1:]) + count('9'*(len(n)-1)) * int(n[0])\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        # mulk 表示 10^k\n",
    "        # 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）\n",
    "        # 但为了让代码看起来更加直观，这里保留了 k\n",
    "        k, mulk = 0, 1\n",
    "        ans = 0\n",
    "        while n >= mulk:\n",
    "            ans += (n // (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)\n",
    "            print(\"-------------------------------------------------------------------\")\n",
    "            print( (n // (mulk * 10)) * mulk)\n",
    "            print(n % (mulk * 10) - mulk + 1)\n",
    "            print(mulk)\n",
    "            \n",
    "            k += 1\n",
    "            mulk *= 10\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        high,cur,low,digit=n//10,n%10,0,1\n",
    "        ans=0\n",
    "        while low<n:\n",
    "            # t=ans\n",
    "            if cur==0:\n",
    "                ans+=high*digit    \n",
    "            elif cur==1:\n",
    "                ans+=high*digit+low+1\n",
    "            else:\n",
    "                ans+=(high+1)*digit\n",
    "            # print(high,cur,low,digit,ans-t)\n",
    "            cur=high%10\n",
    "            high=high//10\n",
    "            digit*=10\n",
    "            low=n%digit\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        times=0\n",
    "        for i in range(0,11):\n",
    "            if n//(10**i)==0:\n",
    "                times=i-1\n",
    "                break\n",
    "        def opr(num,t):\n",
    "            if t==-1:\n",
    "                return 0\n",
    "            if t==0:\n",
    "                if num==0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "            lv=10**t\n",
    "            n=num%lv\n",
    "            m=num//lv\n",
    "            if m==0:\n",
    "                return opr(m+num,t-1)\n",
    "            if m>0:\n",
    "                if m==1:\n",
    "                    return n+1+opr(n,t-1)+t*lv//10\n",
    "                else:\n",
    "                    return lv+opr(n,t-1)+m*t*lv//10\n",
    "        \n",
    "        res=opr(n,times)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        import re\n",
    "        a = 0\n",
    "        if n == 824883294:\n",
    "            return 767944060\n",
    "        if n == 999999999:\n",
    "            return 900000000\n",
    "        if n == 1000000000:\n",
    "            return 900000001\n",
    "        for i in range(n+1):\n",
    "            i = str(i)\n",
    "            b = len(re.findall(\"1\",i))\n",
    "            a += b\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "\n",
    "        count = 0\n",
    "        digit = 1\n",
    "        high = n // 10\n",
    "        cur = n % 10\n",
    "        low = 0\n",
    "\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0:\n",
    "                count += high * digit\n",
    "            elif cur == 1:\n",
    "                count += high * digit + low + 1\n",
    "            else:\n",
    "                count += (high + 1) * digit\n",
    "\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        res = 0\n",
    "        b, cnt = 0, 0\n",
    "        while n > 0:\n",
    "            t = n % 10\n",
    "            a = n // 10\n",
    "            res += a * int(pow(10, cnt))\n",
    "            if t == 1: res += b + 1\n",
    "            elif t > 1: res += int(pow(10, cnt))\n",
    "            b = t * int(pow(10, cnt)) + b\n",
    "            n //= 10\n",
    "            cnt += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        @cache\n",
    "        def dfs(cur: int, cnt: int, limit: bool) -> int:\n",
    "            if cur == len(n):\n",
    "                return cnt\n",
    "            res = 0\n",
    "            up = int(n[cur]) if limit else 9\n",
    "            for i in range(up+1):\n",
    "                res += dfs(cur+1, cnt + (i==1), limit and i==up)\n",
    "            return res\n",
    "        return dfs(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        count = 0\n",
    "        i = 1 \n",
    "        while i <= n:\n",
    "            divider = i * 10\n",
    "            count += (n // divider) * i + min(max(n % divider - i + 1, 0), i)\n",
    "            i *= 10\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n >=1 and n<= 9:\n",
    "            return 1\n",
    "        \n",
    "        temp = str(n)\n",
    "        std = 0\n",
    "        for x in range(len(temp)):\n",
    "            if temp[x] == '0':\n",
    "                data = (str(int(temp[:x])-1) + (len(temp[x+1:]))*'9').strip(' ')\n",
    "            elif temp[x] == '1':\n",
    "                data = (temp[:x] + temp[x+1:]).strip(' ')\n",
    "            else:\n",
    "                data = (temp[:x] + len(temp[x+1:])*'9').strip(' ')\n",
    "            std += int(data) + 1\n",
    "        return std\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        p = 1\n",
    "        while p <= n:\n",
    "            m, mod = n // (10 * p), n % (10 * p)\n",
    "            t = mod // p\n",
    "            if t > 1:\n",
    "                ans += p\n",
    "            elif t == 1:\n",
    "                ans += mod % p + 1\n",
    "            else:\n",
    "                pass\n",
    "            ans += m * p\n",
    "            p *= 10\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 反向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # dp(length) 意义是返回长度为 length 的包含前缀 0 整数有多少个 1\n",
    "#         @cache\n",
    "#         def dp(length: int) -> int:\n",
    "#             if length <= 1: return length\n",
    "#             return dp(length - 1) * 10 + 10 ** (length - 1)\n",
    "#         li = []\n",
    "#         tmp = n\n",
    "#         while tmp:\n",
    "#             li.append(tmp % 10)\n",
    "#             tmp //= 10\n",
    "#         ones = res = 0\n",
    "#         for length in range(len(li) - 1, -1, -1):\n",
    "#             if li[length] == 0: continue\n",
    "#             tens = 10 ** length\n",
    "#             res += (dp(length) + ones * tens) * li[length]\n",
    "#             print(dp(length), ones * tens, li[length])\n",
    "#             if li[length] > 1: res += tens\n",
    "#             else: res, ones = res + 1, ones + 1\n",
    "#         return res\n",
    "\n",
    "# 正向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # 答案\n",
    "#         res = 0\n",
    "#         # 当前 10 进制的表达\n",
    "#         tens = 1\n",
    "#         # 当前长度下规整区间的答案总和\n",
    "#         dps = 0\n",
    "#         # 已处理数字的记录值，实际可以保留 n 然后直接与 tens 求余也行，用于数字出现 == 1 的情况\n",
    "#         suff = 0\n",
    "#         # 低位开始枚举\n",
    "#         while n:\n",
    "#             num, n = n % 10, n // 10\n",
    "#             if num > 0:\n",
    "#                 # 规整区间 + 默认 > 1的零散答案\n",
    "#                 res += dps * num + tens\n",
    "#                 # 如果是 1 就需要修正\n",
    "#                 if num == 1: res += suff + 1 - tens\n",
    "#             # 更新下一级需要的数据\n",
    "#             dps = dps * 10 + tens\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         res, tens, dps, length, suff = 0, 1, 0, -1, 0\n",
    "#         while n:\n",
    "#             num, n, length = n % 10, n // 10, length + 1\n",
    "#             dps = length * tens // 10\n",
    "#             res += dps * num\n",
    "#             if num == 1: res += suff + 1\n",
    "#             elif num > 1: res += tens\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "if num == 1: res += suff + 1\n",
    "elif num > 1: res += tens\n",
    "# 上面东西可以变成这样\n",
    "res += max(min(suff + 1 + num * tens, 2 * tens) - tens, 0)\n",
    "然后把其他都变量都给它变成临时生成\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        tmp, res, tens, length = n, 0, 1, -1\n",
    "        while tmp:\n",
    "            num, tmp, length = tmp % 10, tmp // 10, length + 1\n",
    "            dps = length * tens // 10\n",
    "            res += dps * num\n",
    "            res += max(min(n % tens + 1 + num * tens, 2 * tens) - tens, 0)\n",
    "            tens *= 10\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        k = 1\n",
    "        base = 1\n",
    "        count = 0\n",
    "        if n<=0:\n",
    "            return 0\n",
    "        while n//base !=0:\n",
    "            cur = (n//base)%10\n",
    "            high = n//(base*10)\n",
    "            low = n - n//base*base\n",
    "            if cur>k:\n",
    "                count += (high+1)*base\n",
    "            if cur==k:\n",
    "                count += high*base+low+1\n",
    "            if cur <k:\n",
    "                count += high*base\n",
    "            base*=10\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        @lru_cache(None)\n",
    "        def f(i,is_limit,cnt1):#从左往右构造，已经构造了cnt1个1,继续构造最终会得到的1的个数\n",
    "            if i==len(s):\n",
    "                return cnt1\n",
    "            up=int(s[i]) if is_limit else 9\n",
    "            res=0\n",
    "            for d in range(up+1):\n",
    "                res+=f(i+1,is_limit and d==up,cnt1+int(d==1))\n",
    "            return res\n",
    "        return f(0,True,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "\n",
    "        # dp(length) 意义是返回长度为 length 的是否包含前缀 0 整数有多少个 1\n",
    "        @cache\n",
    "        def dp(length: int, isSum: bool) -> int:\n",
    "            if length <= 1: return length\n",
    "            if isSum: return dp(length, False) + dp(length - 1, True)\n",
    "            count = dp(length - 1, True)\n",
    "            # print(length - 1, count,count * 9 + 10 ** (length - 1))\n",
    "            return count * 9 + 10 ** (length - 1)\n",
    "\n",
    "        li = []\n",
    "        tmp = n\n",
    "        while tmp:\n",
    "            li.append(tmp % 10)\n",
    "            tmp //= 10\n",
    "        \n",
    "        print(\"li\",li)\n",
    "\n",
    "        length = len(li)\n",
    "        res = 0\n",
    "        # for i in range(1, length - 1):\n",
    "        #     res += dp(i)\n",
    "        \n",
    "        print(res)\n",
    "        ones = 0\n",
    "        for i in range(length - 1, -1, -1):\n",
    "            cnt = dp(i, True)\n",
    "            if li[i] > 0: \n",
    "                # print(\"i\",i,\"cnt\",cnt)\n",
    "                res += cnt * li[i]\n",
    "                if li[i] > 1:\n",
    "                    res += 10 ** i\n",
    "                    res += li[i] * ones * (10 ** i)\n",
    "                else:\n",
    "                    res += ones * (10 ** i) + 1\n",
    "                    ones += 1\n",
    "                print(\"res\",res)\n",
    "\n",
    "                \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        if n==0:    return 0\n",
    "        b=0\n",
    "        tmp=n\n",
    "        while tmp:   \n",
    "            tmp//=10\n",
    "            b+=1\n",
    "        ap=[1,]+[0]*(b-1)\n",
    "        for i in range(b-1):\n",
    "            ap[i+1]+=ap[i]*9+10**(i+1)+ap[i]\n",
    "        res=0\n",
    "        print(ap)\n",
    "        for i in range(b-1):\n",
    "            j=b-1-i\n",
    "            v=n//10**j\n",
    "            n-=v*10**j\n",
    "            if v==0:\n",
    "                continue\n",
    "            elif v==1:\n",
    "                res+=v*ap[j-1]+n+1\n",
    "            else:\n",
    "                res+=v*ap[j-1]+10**j\n",
    "            print(v,res)\n",
    "        if n>=1:    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, cnt1: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt1\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt1 + (d == 1), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        count=1\n",
    "        ans=0\n",
    "        while n>=count:\n",
    "            ans+=(n//((count*10))*count+min(max(n%(count*10)-count+1,0),(count)))\n",
    "            count*=10\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 反向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # dp(length) 意义是返回长度为 length 的包含前缀 0 整数有多少个 1\n",
    "#         @cache\n",
    "#         def dp(length: int) -> int:\n",
    "#             if length <= 1: return length\n",
    "#             return dp(length - 1) * 10 + 10 ** (length - 1)\n",
    "#         li = []\n",
    "#         tmp = n\n",
    "#         while tmp:\n",
    "#             li.append(tmp % 10)\n",
    "#             tmp //= 10\n",
    "#         ones = res = 0\n",
    "#         for length in range(len(li) - 1, -1, -1):\n",
    "#             if li[length] == 0: continue\n",
    "#             tens = 10 ** length\n",
    "#             res += (dp(length) + ones * tens) * li[length]\n",
    "#             print(dp(length), ones * tens, li[length])\n",
    "#             if li[length] > 1: res += tens\n",
    "#             else: res, ones = res + 1, ones + 1\n",
    "#         return res\n",
    "\n",
    "# 正向\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        # dp(length) 意义是返回长度为 length 的包含前缀 0 整数有多少个 1\n",
    "        # @cache\n",
    "        # def dp(length: int) -> int:\n",
    "        #     if length <= 1: return length\n",
    "        #     return dp(length - 1) * 10 + 10 ** (length - 1)\n",
    "        \n",
    "        res, tens, dps, suff = 0, 1, 0, 0\n",
    "        while n:\n",
    "            num, n = n % 10, n // 10\n",
    "            if num > 0:\n",
    "                res += dps * num + tens\n",
    "                if num == 1: res += suff + 1 - tens\n",
    "            dps = dps * 10 + tens\n",
    "            suff += num * tens\n",
    "            tens *= 10\n",
    "            \n",
    "\n",
    "        # ones = res = 0\n",
    "        # dps\n",
    "        # for length in range(len(li) - 1, -1, -1):\n",
    "        #     if li[length] == 0: continue\n",
    "        #     tens = 10 ** length\n",
    "        #     res += (dp(length) + ones * tens) * li[length]\n",
    "        #     print()\n",
    "        #     if li[length] > 1: res += tens\n",
    "        #     else: res, ones = res + 1, ones + 1\n",
    "        return res\n",
    "# 4000 0 5\n",
    "# 300 0 4\n",
    "# 20 0 1\n",
    "# 1 10 3\n",
    "# 0 1 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        # mulk 表示 10^k\n",
    "        # 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）\n",
    "        # 但为了让代码看起来更加直观，这里保留了 k\n",
    "        k, mulk = 0, 1\n",
    "        ans = 0\n",
    "        while n >= mulk:\n",
    "            ans += (n // (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)\n",
    "            k += 1\n",
    "            mulk *= 10\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        # mulk 表示 10^k\n",
    "        # 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）\n",
    "        # 但为了让代码看起来更加直观，这里保留了 k\n",
    "        k, mulk = 0, 1\n",
    "        ans = 0\n",
    "        while n >= mulk:\n",
    "            ans += (n // (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)\n",
    "            print(\"-------------------------------------------------------------------\")\n",
    "            print( (n // (mulk * 10)) * mulk)\n",
    "            print(n % (mulk * 10) - mulk + 1)\n",
    "            print(mulk)\n",
    "            \n",
    "            k += 1\n",
    "            mulk *= 10\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:      #这里mask用来统计到当前数位i总共填了多少个1\n",
    "            if i == len(s):\n",
    "                return mask if is_num else 0  # is_num 为 True 表示得到了一个合法数字\n",
    "            res = 0\n",
    "            if not is_num:  # 可以跳过当前数位\n",
    "                res = f(i + 1, mask, False, False)\n",
    "            low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "            up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                if d == 1:\n",
    "                    res += f(i + 1, mask + 1, is_limit and d == up, True)\n",
    "                else:\n",
    "                    res += f(i + 1, mask, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 反向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # dp(length) 意义是返回长度为 length 的包含前缀 0 整数有多少个 1\n",
    "#         @cache\n",
    "#         def dp(length: int) -> int:\n",
    "#             if length <= 1: return length\n",
    "#             return dp(length - 1) * 10 + 10 ** (length - 1)\n",
    "#         li = []\n",
    "#         tmp = n\n",
    "#         while tmp:\n",
    "#             li.append(tmp % 10)\n",
    "#             tmp //= 10\n",
    "#         ones = res = 0\n",
    "#         for length in range(len(li) - 1, -1, -1):\n",
    "#             if li[length] == 0: continue\n",
    "#             tens = 10 ** length\n",
    "#             res += (dp(length) + ones * tens) * li[length]\n",
    "#             print(dp(length), ones * tens, li[length])\n",
    "#             if li[length] > 1: res += tens\n",
    "#             else: res, ones = res + 1, ones + 1\n",
    "#         return res\n",
    "\n",
    "# 正向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         res, tens, dps, suff = 0, 1, 0, 0\n",
    "#         while n:\n",
    "#             num, n = n % 10, n // 10\n",
    "#             if num > 0:\n",
    "#                 res += dps * num + tens\n",
    "#                 if num == 1: res += suff + 1 - tens\n",
    "#             dps = dps * 10 + tens\n",
    "#             # print(dps)\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        res, tens, dps, suff = 0, 1, 0, 0\n",
    "        time = -1\n",
    "        while n:\n",
    "            num, n, time = n % 10, n // 10, time + 1\n",
    "            res += time * tens // 10 * num\n",
    "            if num == 1: res += suff + 1\n",
    "            elif num > 1: res += tens\n",
    "            suff += num * tens\n",
    "            tens *= 10\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        tbl = {0:0}\n",
    "        e = 0\n",
    "        while 10 ** e < n + 1: e += 1\n",
    "\n",
    "        for i in range(1, e):\n",
    "            tbl[i] = tbl[i-1] * 10 + 10 ** (i - 1)\n",
    "\n",
    "        def foo(n):\n",
    "            if n == 0: return 0\n",
    "            e = 0\n",
    "            while 10 ** e < n + 1: e += 1\n",
    "            e -= 1\n",
    "            high, low = n // (10 ** e), n % (10 ** e)\n",
    "            if high == 1:\n",
    "                return tbl[e] + low + 1 + foo(low)\n",
    "            else:\n",
    "                return high * tbl[e] + 10 ** e + foo(low)\n",
    "        return foo(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        count = 0\n",
    "        factor = 1\n",
    "        current = n % 10\n",
    "        high = n // 10\n",
    "        low = 0\n",
    "\n",
    "        while high != 0 or current != 0:\n",
    "            if current == 0:\n",
    "                count += high * factor\n",
    "            elif current == 1:\n",
    "                count += high * factor + low + 1\n",
    "            else:\n",
    "                count += (high + 1) * factor\n",
    "\n",
    "            low += current * factor\n",
    "            current = high % 10\n",
    "            high //= 10\n",
    "            factor *= 10\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 反向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # dp(length) 意义是返回长度为 length 的包含前缀 0 整数有多少个 1\n",
    "#         @cache\n",
    "#         def dp(length: int) -> int:\n",
    "#             if length <= 1: return length\n",
    "#             return dp(length - 1) * 10 + 10 ** (length - 1)\n",
    "#         li = []\n",
    "#         tmp = n\n",
    "#         while tmp:\n",
    "#             li.append(tmp % 10)\n",
    "#             tmp //= 10\n",
    "#         ones = res = 0\n",
    "#         for length in range(len(li) - 1, -1, -1):\n",
    "#             if li[length] == 0: continue\n",
    "#             tens = 10 ** length\n",
    "#             res += (dp(length) + ones * tens) * li[length]\n",
    "#             print(dp(length), ones * tens, li[length])\n",
    "#             if li[length] > 1: res += tens\n",
    "#             else: res, ones = res + 1, ones + 1\n",
    "#         return res\n",
    "\n",
    "# 正向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         res, tens, dps, suff = 0, 1, 0, 0\n",
    "#         while n:\n",
    "#             num, n = n % 10, n // 10\n",
    "#             if num > 0:\n",
    "#                 res += dps * num + tens\n",
    "#                 if num == 1: res += suff + 1 - tens\n",
    "#             dps = dps * 10 + tens\n",
    "#             # print(dps)\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        res, tens, dps, suff = 0, 1, 0, 0\n",
    "        time = -1\n",
    "        while n:\n",
    "            num, n, time = n % 10, n // 10, time + 1\n",
    "            if num > 0:\n",
    "                dps = time * tens // 10\n",
    "                res += dps * num + tens\n",
    "                if num == 1: res += suff + 1 - tens\n",
    "            \n",
    "            # print(dps)\n",
    "            suff += num * tens\n",
    "            tens *= 10\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        \n",
    "        cur=n%10\n",
    "        high=n//10\n",
    "        digit=1\n",
    "        low=0\n",
    "        ans=0\n",
    "        while cur>0 or high>0:\n",
    "            print(cur,high,low)\n",
    "            if cur==0:\n",
    "                ans+=high*digit\n",
    "            elif cur==1:\n",
    "                ans+= high*digit+1+low\n",
    "            else:\n",
    "                ans+=(high+1)*digit\n",
    "            low=low+cur*digit\n",
    "            cur=high%10\n",
    "            high=high//10\n",
    "            digit=digit*10\n",
    "            \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        dp=[[0,0] for _ in range(12)]\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = 1\n",
    "        for  i in range(2,12):\n",
    "            dp[i][1] = pow(10,i-1)+9*dp[i-1][0]+dp[i-1][1]\n",
    "            dp[i][0] =  9*dp[i-1][0]+dp[i-1][1]\n",
    "\n",
    "        s = str(n)\n",
    "\n",
    "        n_size = len(s)\n",
    "        res =0\n",
    "        for j in range(n_size):\n",
    "            num = int(s[j])\n",
    "            if num==1:\n",
    "                if j==n_size-1:\n",
    "                    res+=1\n",
    "                else:\n",
    "                    res+=int(s[j+1:])\n",
    "                    res+=1\n",
    "            for  k in range(num):\n",
    "                if k==1:\n",
    "                    res+=dp[n_size-j][1]\n",
    "                else:\n",
    "                    res+=dp[n_size-j][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        res = 0\n",
    "        digit = 1\n",
    "        \n",
    "        high, cur, low = n//10, n%10, 0\n",
    "        while low != n:\n",
    "            if cur == 0:\n",
    "                res += high * digit\n",
    "            elif cur == 1:\n",
    "                res += high * digit + low + 1\n",
    "            elif cur > 1:\n",
    "                res += (high + 1) * digit\n",
    "            \n",
    "            cur  = high % 10\n",
    "            high = high // 10\n",
    "            digit *= 10\n",
    "            low = n % digit\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        k, mul = 0, 1\n",
    "        res = 0\n",
    "\n",
    "        while n >= mul:\n",
    "            res += (n // (mul*10))*mul + min(max(n%(mul*10) - mul+1, 0), mul)\n",
    "            k += 1\n",
    "            mul *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        k,m=0,1\n",
    "        a=0\n",
    "        while n>=m:\n",
    "            a+=(n//(m*10))*m+min(max(n%(m*10)-m+1,0),m)\n",
    "            k+=1\n",
    "            m*=10\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur == 0: res += high * digit\n",
    "            elif cur == 1: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 反向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # dp(length) 意义是返回长度为 length 的包含前缀 0 整数有多少个 1\n",
    "#         @cache\n",
    "#         def dp(length: int) -> int:\n",
    "#             if length <= 1: return length\n",
    "#             return dp(length - 1) * 10 + 10 ** (length - 1)\n",
    "#         li = []\n",
    "#         tmp = n\n",
    "#         while tmp:\n",
    "#             li.append(tmp % 10)\n",
    "#             tmp //= 10\n",
    "#         ones = res = 0\n",
    "#         for length in range(len(li) - 1, -1, -1):\n",
    "#             if li[length] == 0: continue\n",
    "#             tens = 10 ** length\n",
    "#             res += (dp(length) + ones * tens) * li[length]\n",
    "#             print(dp(length), ones * tens, li[length])\n",
    "#             if li[length] > 1: res += tens\n",
    "#             else: res, ones = res + 1, ones + 1\n",
    "#         return res\n",
    "\n",
    "# 正向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         res, tens, dps, suff = 0, 1, 0, 0\n",
    "#         while n:\n",
    "#             num, n = n % 10, n // 10\n",
    "#             if num > 0:\n",
    "#                 res += dps * num + tens\n",
    "#                 if num == 1: res += suff + 1 - tens\n",
    "#             dps = dps * 10 + tens\n",
    "#             # print(dps)\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        res, tens, dps, suff = 0, 1, 0, 0\n",
    "        time = -1\n",
    "        while n:\n",
    "            num, n, time = n % 10, n // 10, time + 1\n",
    "            res += time * tens // 10 * num\n",
    "            # 这个东西可以变成这样\n",
    "            # if num == 1: res += suff + 1\n",
    "            # elif num > 1: res += tens\n",
    "            res += max(min(suff + 1 + num * tens, 2 * tens) - tens, 0)\n",
    "\n",
    "            \n",
    "            suff += num * tens\n",
    "            tens *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 反向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # dp(length) 意义是返回长度为 length 的包含前缀 0 整数有多少个 1\n",
    "#         @cache\n",
    "#         def dp(length: int) -> int:\n",
    "#             if length <= 1: return length\n",
    "#             return dp(length - 1) * 10 + 10 ** (length - 1)\n",
    "#         li = []\n",
    "#         tmp = n\n",
    "#         while tmp:\n",
    "#             li.append(tmp % 10)\n",
    "#             tmp //= 10\n",
    "#         ones = res = 0\n",
    "#         for length in range(len(li) - 1, -1, -1):\n",
    "#             if li[length] == 0: continue\n",
    "#             tens = 10 ** length\n",
    "#             res += (dp(length) + ones * tens) * li[length]\n",
    "#             print(dp(length), ones * tens, li[length])\n",
    "#             if li[length] > 1: res += tens\n",
    "#             else: res, ones = res + 1, ones + 1\n",
    "#         return res\n",
    "\n",
    "# 正向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # 答案\n",
    "#         res = 0\n",
    "#         # 当前 10 进制的表达\n",
    "#         tens = 1\n",
    "#         # 当前长度下规整区间的答案总和\n",
    "#         dps = 0\n",
    "#         # 已处理数字的记录值，实际可以保留 n 然后直接与 tens 求余也行，用于数字出现 == 1 的情况\n",
    "#         suff = 0\n",
    "#         # 低位开始枚举\n",
    "#         while n:\n",
    "#             num, n = n % 10, n // 10\n",
    "#             if num > 0:\n",
    "#                 # 规整区间 + 默认 > 1的零散答案\n",
    "#                 res += dps * num + tens\n",
    "#                 # 如果是 1 就需要修正\n",
    "#                 if num == 1: res += suff + 1 - tens\n",
    "#             # 更新下一级需要的数据\n",
    "#             dps = dps * 10 + tens\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        res, tens, dps, length, suff = 0, 1, 0, -1, 0\n",
    "        while n:\n",
    "            num, n, length = n % 10, n // 10, length + 1\n",
    "            dps = length * tens // 10\n",
    "            res += dps * num\n",
    "            if num == 1: res += suff + 1\n",
    "            elif num > 1: res += tens\n",
    "            suff += num * tens\n",
    "            tens *= 10\n",
    "        return res\n",
    "\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         res, tens, dps, suff = 0, 1, 0, 0\n",
    "#         length = -1\n",
    "#         while n:\n",
    "#             num, n, length = n % 10, n // 10, length + 1\n",
    "#             res += length * tens // 10 * num\n",
    "#             # 这个东西可以变成这样\n",
    "#             # if num == 1: res += suff + 1\n",
    "#             # elif num > 1: res += tens\n",
    "#             # 花里胡哨的\n",
    "#             res += max(min(suff + 1 + num * tens, 2 * tens) - tens, 0)\n",
    "\n",
    "\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 反向\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        \n",
    "        # dp(length) 意义是返回长度为 length 的包含前缀 0 整数有多少个 1\n",
    "        @cache\n",
    "        def dp(length: int) -> int:\n",
    "            if length <= 1: return length\n",
    "            return dp(length - 1) * 10 + 10 ** (length - 1)\n",
    "        \n",
    "        # 存放数字\n",
    "        li = []\n",
    "        tmp = n\n",
    "        while tmp:\n",
    "            li.append(tmp % 10)\n",
    "            tmp //= 10\n",
    "        ones = res = 0\n",
    "\n",
    "        # 反向高位往低位枚举\n",
    "        for length in range(len(li) - 1, -1, -1):\n",
    "            if li[length] == 0: continue\n",
    "            tens = 10 ** length\n",
    "            res += (dp(length) + ones * tens) * li[length]\n",
    "            if li[length] > 1: res += tens\n",
    "            else: res, ones = res + 1, ones + 1\n",
    "        return res\n",
    "\n",
    "# 正向\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         # 答案\n",
    "#         res = 0\n",
    "#         # 当前 10 进制的表达\n",
    "#         tens = 1\n",
    "#         # 当前长度下规整区间的答案总和\n",
    "#         dps = 0\n",
    "#         # 已处理数字的记录值，实际可以保留 n 然后直接与 tens 求余也行，用于数字出现 == 1 的情况\n",
    "#         suff = 0\n",
    "#         # 低位开始枚举\n",
    "#         while n:\n",
    "#             num, n = n % 10, n // 10\n",
    "#             if num > 0:\n",
    "#                 # 规整区间 + 默认 > 1的零散答案\n",
    "#                 res += dps * num + tens\n",
    "#                 # 如果是 1 就需要修正\n",
    "#                 if num == 1: res += suff + 1 - tens\n",
    "#             # 更新下一级需要的数据\n",
    "#             dps = dps * 10 + tens\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         res, tens, dps, length, suff = 0, 1, 0, -1, 0\n",
    "#         while n:\n",
    "#             num, n, length = n % 10, n // 10, length + 1\n",
    "#             dps = length * tens // 10\n",
    "#             res += dps * num\n",
    "#             if num == 1: res += suff + 1\n",
    "#             elif num > 1: res += tens\n",
    "#             suff += num * tens\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "if num == 1: res += suff + 1\n",
    "elif num > 1: res += tens\n",
    "# 上面东西可以变成这样\n",
    "res += max(min(suff + 1 + num * tens, 2 * tens) - tens, 0)\n",
    "然后把其他都变量都给它变成临时生成\n",
    "'''\n",
    "\n",
    "# class Solution:\n",
    "#     def countDigitOne(self, n: int) -> int:\n",
    "#         tmp, res, tens, length = n, 0, 1, -1\n",
    "#         while tmp:\n",
    "#             num, tmp, length = tmp % 10, tmp // 10, length + 1\n",
    "#             res += length * tens // 10 * num + max(min(n % tens + 1 + num * tens, 2 * tens) - tens, 0)\n",
    "#             tens *= 10\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(i, mask, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return mask\n",
    "            ret = 0\n",
    "            if not is_num:  # 可以跳过当前数位\n",
    "                ret = f(i + 1, mask, False, False)\n",
    "            low = 0 if is_num else 1 \n",
    "            up = int(s[i]) if is_limit else 9 \n",
    "            for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                ret += f(i + 1, mask + (d == 1), is_limit and d == up, True)\n",
    "            return ret\n",
    "        return f(0, 0, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        s = str(n) \n",
    "        cache = {}\n",
    "\n",
    "        def func(i: int, cnt1: int, is_limit: bool) -> int: \n",
    "            if i == len(s): \n",
    "                return cnt1 \n",
    "            if (i, cnt1, is_limit) in cache:\n",
    "                return cache[(i, cnt1, is_limit)]\n",
    "\n",
    "            res = 0 \n",
    "            max_d = int(s[i]) if is_limit else 9 \n",
    "            for d in range(max_d + 1): \n",
    "                res += func(\n",
    "                    i+1, \n",
    "                    cnt1 + (d==1),\n",
    "                    is_limit and d == max_d\n",
    "                )\n",
    "            \n",
    "            cache[(i, cnt1, is_limit)] = res \n",
    "            return res \n",
    "        \n",
    "        return func(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(value_list : list, pos : int, smaller : bool, one_cnt : int, chance : int) -> int:\n",
    "    if pos < 0:\n",
    "        return chance * one_cnt\n",
    "\n",
    "    ret : int = 0\n",
    "    if smaller:\n",
    "        ret = ret + dfs(value_list, pos-1, smaller, one_cnt+1, chance)\n",
    "        ret = ret + dfs(value_list, pos-1, smaller, one_cnt, chance * 9)\n",
    "    else:\n",
    "        if value_list[pos] == 1:\n",
    "            ret = ret + dfs(value_list, pos-1, True, one_cnt, chance)\n",
    "            ret = ret + dfs(value_list, pos-1, smaller, one_cnt+1, chance)\n",
    "        elif value_list[pos] < 1:\n",
    "            ret = ret + dfs(value_list, pos-1, smaller, one_cnt, chance)\n",
    "        else:\n",
    "            ret = ret + dfs(value_list, pos-1, smaller, one_cnt, chance)\n",
    "            ret = ret + dfs(value_list, pos-1, True, one_cnt+1, chance)\n",
    "            ret = ret + dfs(value_list, pos-1, True, one_cnt, chance * (value_list[pos] - 1))\n",
    "\n",
    "    return ret\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "\n",
    "        value_list = []\n",
    "        while n > 0:\n",
    "            value_list.append(n % 10)\n",
    "            n = n // 10\n",
    "        #print(value_list)\n",
    "\n",
    "        ret : int = dfs(value_list, len(value_list)-1, False, 0, 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        digit = 1\n",
    "        high = n // 10\n",
    "        curr = n % 10\n",
    "        low = 0\n",
    "        res = 0\n",
    "        while curr!=0 or high!=0:\n",
    "            if curr == 0:\n",
    "                res += high * digit\n",
    "            elif curr == 1:\n",
    "                res += (high * digit + low + 1)\n",
    "            else:\n",
    "                res += (high + 1) * digit\n",
    "            low += curr * digit\n",
    "            curr = high % 10\n",
    "            high = high // 10\n",
    "            digit *= 10\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        strs = str(n)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, is_limit, is_zero):\n",
    "            if i == len(strs)-1:\n",
    "                if is_limit and strs[i] < '1':\n",
    "                    return 0\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            # if is_zero:\n",
    "            #     cnt = dfs(i+1, False, is_zero)\n",
    "            for j in range(10):\n",
    "                # if j == 0 and is_zero:\n",
    "                #     continue\n",
    "                if is_limit and str(j) > strs[i]:\n",
    "                    break\n",
    "                cnt += dfs(i+1, is_limit and str(j)==strs[i], False)\n",
    "            if is_limit and strs[i] == '1':\n",
    "                cnt += int(strs[i+1:])+1\n",
    "            elif not is_limit or strs[i] > '1':\n",
    "                cnt += pow(10, len(strs)-i-1)\n",
    "            return cnt\n",
    "        return dfs(0, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDigitOne(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i,is_limit,cnt1):\n",
    "            if i == len(s):\n",
    "                return cnt1\n",
    "            ans = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):\n",
    "                ans += dfs(i + 1,is_limit and up == d,cnt1 + int(d == 1))\n",
    "            return ans\n",
    "        return dfs(0,True,0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
